/*
 * contrib/intarray/_intbig_gist.c
 */
#include "postgres.h"

#include "_int.h"
#include "access/gist.h"
#include "access/reloptions.h"
#include "access/stratnum.h"
#include "port/pg_bitutils.h"

#define GETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer((vec)->vector[(pos)].key))
/*
** _intbig 方法
*/
PG_FUNCTION_INFO_V1(g_intbig_consistent);
PG_FUNCTION_INFO_V1(g_intbig_compress);
PG_FUNCTION_INFO_V1(g_intbig_decompress);
PG_FUNCTION_INFO_V1(g_intbig_penalty);
PG_FUNCTION_INFO_V1(g_intbig_picksplit);
PG_FUNCTION_INFO_V1(g_intbig_union);
PG_FUNCTION_INFO_V1(g_intbig_same);
PG_FUNCTION_INFO_V1(g_intbig_options);

PG_FUNCTION_INFO_V1(_intbig_in);
PG_FUNCTION_INFO_V1(_intbig_out);

Datum _intbig_in(PG_FUNCTION_ARGS)
{
	ereport(ERROR,
			(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
			 errmsg("_intbig_in() not implemented")));
	PG_RETURN_DATUM(0);
}

Datum _intbig_out(PG_FUNCTION_ARGS)
{
	ereport(ERROR,
			(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
			 errmsg("_intbig_out() not implemented")));
	PG_RETURN_DATUM(0);
}

static GISTTYPE *
fc__intbig_alloc(bool fc_allistrue, int fc_siglen, BITVECP fc_sign)
{
	int			fc_flag = fc_allistrue ? ALLISTRUE : 0;
	int			fc_size = CALCGTSIZE(fc_flag, fc_siglen);
	GISTTYPE   *fc_res = (GISTTYPE *) palloc(fc_size);

	SET_VARSIZE(fc_res, fc_size);
	fc_res->flag = fc_flag;

	if (!fc_allistrue)
	{
		if (fc_sign)
			memcpy(GETSIGN(fc_res), fc_sign, fc_siglen);
		else
			memset(GETSIGN(fc_res), 0, fc_siglen);
	}

	return fc_res;
}


/*********************************************************************
** intbig 函数
*********************************************************************/
static bool fc__intbig_overlap(GISTTYPE *fc_a, ArrayType *fc_b, int fc_siglen)
{
	int			fc_num = ARRNELEMS(fc_b);
	int32	   *fc_ptr = ARRPTR(fc_b);

	CHECKARRVALID(fc_b);

	while (fc_num--)
	{
		if (GETBIT(GETSIGN(fc_a), HASHVAL(*fc_ptr, fc_siglen)))
			return true;
		fc_ptr++;
	}

	return false;
}

static bool fc__intbig_contains(GISTTYPE *fc_a, ArrayType *fc_b, int fc_siglen)
{
	int			fc_num = ARRNELEMS(fc_b);
	int32	   *fc_ptr = ARRPTR(fc_b);

	CHECKARRVALID(fc_b);

	while (fc_num--)
	{
		if (!GETBIT(GETSIGN(fc_a), HASHVAL(*fc_ptr, fc_siglen)))
			return false;
		fc_ptr++;
	}

	return true;
}

Datum g_intbig_same(PG_FUNCTION_ARGS)
{
	GISTTYPE   *fc_a = (GISTTYPE *) PG_GETARG_POINTER(0);
	GISTTYPE   *fc_b = (GISTTYPE *) PG_GETARG_POINTER(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);
	int			fc_siglen = GET_SIGLEN();

	if (ISALLTRUE(fc_a) && ISALLTRUE(fc_b))
		*fc_result = true;
	else if (ISALLTRUE(fc_a))
		*fc_result = false;
	else if (ISALLTRUE(fc_b))
		*fc_result = false;
	else
	{
		int32		fc_i;
		BITVECP		fc_sa = GETSIGN(fc_a),
					fc_sb = GETSIGN(fc_b);

		*fc_result = true;
		LOOPBYTE(fc_siglen)
		{
			if (fc_sa[fc_i] != fc_sb[fc_i])
			{
				*fc_result = false;
				break;
			}
		}
	}
	PG_RETURN_POINTER(fc_result);
}

Datum g_intbig_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	int			fc_siglen = GET_SIGLEN();

	if (fc_entry->leafkey)
	{
		GISTENTRY  *fc_retval;
		ArrayType  *fc_in = DatumGetArrayTypeP(fc_entry->key);
		int32	   *fc_ptr;
		int			fc_num;
		GISTTYPE   *fc_res = fc__intbig_alloc(false, fc_siglen, NULL);

		CHECKARRVALID(fc_in);
		if (ARRISEMPTY(fc_in))
		{
			fc_ptr = NULL;
			fc_num = 0;
		}
		else
		{
			fc_ptr = ARRPTR(fc_in);
			fc_num = ARRNELEMS(fc_in);
		}

		while (fc_num--)
		{
			HASH(GETSIGN(fc_res), *fc_ptr, fc_siglen);
			fc_ptr++;
		}

		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);

		PG_RETURN_POINTER(fc_retval);
	}
	else if (!ISALLTRUE(DatumGetPointer(fc_entry->key)))
	{
		GISTENTRY  *fc_retval;
		int			fc_i;
		BITVECP		fc_sign = GETSIGN(DatumGetPointer(fc_entry->key));
		GISTTYPE   *fc_res;

		LOOPBYTE(fc_siglen)
		{
			if ((fc_sign[fc_i] & 0xff) != 0xff)
				PG_RETURN_POINTER(fc_entry);
		}

		fc_res = fc__intbig_alloc(true, fc_siglen, fc_sign);
		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);

		PG_RETURN_POINTER(fc_retval);
	}

	PG_RETURN_POINTER(fc_entry);
}


static int32 fc_sizebitvec(BITVECP fc_sign, int fc_siglen)
{
	return pg_popcount(fc_sign, fc_siglen);
}

static int fc_hemdistsign(BITVECP fc_a, BITVECP fc_b, int fc_siglen)
{
	int			fc_i,
				fc_diff,
				fc_dist = 0;

	LOOPBYTE(fc_siglen)
	{
		fc_diff = (unsigned char) (fc_a[fc_i] ^ fc_b[fc_i]);
		/* 在这里使用 popcount 函数不太可能获胜 */
		fc_dist += pg_number_of_ones[fc_diff];
	}
	return fc_dist;
}

static int fc_hemdist(GISTTYPE *fc_a, GISTTYPE *fc_b, int fc_siglen)
{
	if (ISALLTRUE(fc_a))
	{
		if (ISALLTRUE(fc_b))
			return 0;
		else
			return SIGLENBIT(fc_siglen) - fc_sizebitvec(GETSIGN(fc_b), fc_siglen);
	}
	else if (ISALLTRUE(fc_b))
		return SIGLENBIT(fc_siglen) - fc_sizebitvec(GETSIGN(fc_a), fc_siglen);

	return fc_hemdistsign(GETSIGN(fc_a), GETSIGN(fc_b), fc_siglen);
}

Datum g_intbig_decompress(PG_FUNCTION_ARGS)
{
	PG_RETURN_DATUM(PG_GETARG_DATUM(0));
}

static int32 fc_unionkey(BITVECP fc_sbase, GISTTYPE *fc_add, int fc_siglen)
{
	int32		fc_i;
	BITVECP		fc_sadd = GETSIGN(fc_add);

	if (ISALLTRUE(fc_add))
		return 1;
	LOOPBYTE(fc_siglen)
		fc_sbase[fc_i] |= fc_sadd[fc_i];
	return 0;
}

Datum g_intbig_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int		   *fc_size = (int *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	int32		fc_i;
	GISTTYPE   *fc_result = fc__intbig_alloc(false, fc_siglen, NULL);
	BITVECP		fc_base = GETSIGN(fc_result);

	for (fc_i = 0; fc_i < fc_entryvec->n; fc_i++)
	{
		if (fc_unionkey(fc_base, GETENTRY(fc_entryvec, fc_i), fc_siglen))
		{
			fc_result->flag |= ALLISTRUE;
			SET_VARSIZE(fc_result, CALCGTSIZE(ALLISTRUE, fc_siglen));
			break;
		}
	}

	*fc_size = VARSIZE(fc_result);

	PG_RETURN_POINTER(fc_result);
}

Datum g_intbig_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* 始终 ISSIGNKEY */
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_penalty = (float *) PG_GETARG_POINTER(2);
	GISTTYPE   *fc_origval = (GISTTYPE *) DatumGetPointer(fc_origentry->key);
	GISTTYPE   *fc_newval = (GISTTYPE *) DatumGetPointer(fc_newentry->key);
	int			fc_siglen = GET_SIGLEN();

	*fc_penalty = fc_hemdist(fc_origval, fc_newval, fc_siglen);
	PG_RETURN_POINTER(fc_penalty);
}


typedef struct
{
	OffsetNumber pos;
	int32		cost;
} SPLITCOST;

static int fc_comparecost(const void *fc_a, const void *fc_b)
{
	return ((const SPLITCOST *) fc_a)->cost - ((const SPLITCOST *) fc_b)->cost;
}


Datum g_intbig_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	OffsetNumber fc_k,
				fc_j;
	GISTTYPE   *fc_datum_l,
			   *fc_datum_r;
	BITVECP		fc_union_l,
				fc_union_r;
	int32		fc_size_alpha,
				fc_size_beta;
	int32		fc_size_waste,
				fc_waste = -1;
	int32		fc_nbytes;
	OffsetNumber fc_seed_1 = 0,
				fc_seed_2 = 0;
	OffsetNumber *fc_left,
			   *fc_right;
	OffsetNumber fc_maxoff;
	BITVECP		fc_ptr;
	int			fc_i;
	SPLITCOST  *fc_costvector;
	GISTTYPE   *fc__k,
			   *fc__j;

	fc_maxoff = fc_entryvec->n - 2;
	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);

	for (fc_k = FirstOffsetNumber; fc_k < fc_maxoff; fc_k = OffsetNumberNext(fc_k))
	{
		fc__k = GETENTRY(fc_entryvec, fc_k);
		for (fc_j = OffsetNumberNext(fc_k); fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
		{
			fc_size_waste = fc_hemdist(fc__k, GETENTRY(fc_entryvec, fc_j), fc_siglen);
			if (fc_size_waste > fc_waste)
			{
				fc_waste = fc_size_waste;
				fc_seed_1 = fc_k;
				fc_seed_2 = fc_j;
			}
		}
	}

	fc_left = fc_v->spl_left;
	fc_v->spl_nleft = 0;
	fc_right = fc_v->spl_right;
	fc_v->spl_nright = 0;

	if (fc_seed_1 == 0 || fc_seed_2 == 0)
	{
		fc_seed_1 = 1;
		fc_seed_2 = 2;
	}

	/* 形成初始 .. */
	fc_datum_l = fc__intbig_alloc(ISALLTRUE(GETENTRY(fc_entryvec, fc_seed_1)), fc_siglen,
							GETSIGN(GETENTRY(fc_entryvec, fc_seed_1)));
	fc_datum_r = fc__intbig_alloc(ISALLTRUE(GETENTRY(fc_entryvec, fc_seed_2)), fc_siglen,
							GETSIGN(GETENTRY(fc_entryvec, fc_seed_2)));

	fc_maxoff = OffsetNumberNext(fc_maxoff);
	/* 在 ... 之前排序 */
	fc_costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * fc_maxoff);
	for (fc_j = FirstOffsetNumber; fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
	{
		fc_costvector[fc_j - 1].pos = fc_j;
		fc__j = GETENTRY(fc_entryvec, fc_j);
		fc_size_alpha = fc_hemdist(fc_datum_l, fc__j, fc_siglen);
		fc_size_beta = fc_hemdist(fc_datum_r, fc__j, fc_siglen);
		fc_costvector[fc_j - 1].cost = Abs(fc_size_alpha - fc_size_beta);
	}
	qsort((void *) fc_costvector, fc_maxoff, sizeof(SPLITCOST), fc_comparecost);

	fc_union_l = GETSIGN(fc_datum_l);
	fc_union_r = GETSIGN(fc_datum_r);

	for (fc_k = 0; fc_k < fc_maxoff; fc_k++)
	{
		fc_j = fc_costvector[fc_k].pos;
		if (fc_j == fc_seed_1)
		{
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
			continue;
		}
		else if (fc_j == fc_seed_2)
		{
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
			continue;
		}
		fc__j = GETENTRY(fc_entryvec, fc_j);
		fc_size_alpha = fc_hemdist(fc_datum_l, fc__j, fc_siglen);
		fc_size_beta = fc_hemdist(fc_datum_r, fc__j, fc_siglen);

		if (fc_size_alpha < fc_size_beta + WISH_F(fc_v->spl_nleft, fc_v->spl_nright, 0.00001))
		{
			if (ISALLTRUE(fc_datum_l) || ISALLTRUE(fc__j))
			{
				if (!ISALLTRUE(fc_datum_l))
					MemSet((void *) fc_union_l, 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = GETSIGN(fc__j);
				LOOPBYTE(fc_siglen)
					fc_union_l[fc_i] |= fc_ptr[fc_i];
			}
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
		}
		else
		{
			if (ISALLTRUE(fc_datum_r) || ISALLTRUE(fc__j))
			{
				if (!ISALLTRUE(fc_datum_r))
					MemSet((void *) fc_union_r, 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = GETSIGN(fc__j);
				LOOPBYTE(fc_siglen)
					fc_union_r[fc_i] |= fc_ptr[fc_i];
			}
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
		}
	}

	*fc_right = *fc_left = FirstOffsetNumber;
	pfree(fc_costvector);

	fc_v->spl_ldatum = PointerGetDatum(fc_datum_l);
	fc_v->spl_rdatum = PointerGetDatum(fc_datum_r);

	PG_RETURN_POINTER(fc_v);
}

Datum g_intbig_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	ArrayType  *fc_query = PG_GETARG_ARRAYTYPE_P(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	int			fc_siglen = GET_SIGLEN();
	bool		fc_retval;

	/* 此函数处理的所有情况都是不准确的 */
	*fc_recheck = true;

	if (ISALLTRUE(DatumGetPointer(fc_entry->key)))
		PG_RETURN_BOOL(true);

	if (fc_strategy == BooleanSearchStrategy)
	{
		fc_retval = signconsistent((QUERYTYPE *) fc_query,
								GETSIGN(DatumGetPointer(fc_entry->key)),
								fc_siglen,
								false);
		PG_FREE_IF_COPY(fc_query, 1);
		PG_RETURN_BOOL(fc_retval);
	}

	CHECKARRVALID(fc_query);

	switch (fc_strategy)
	{
		case RTOverlapStrategyNumber:
			fc_retval = fc__intbig_overlap((GISTTYPE *) DatumGetPointer(fc_entry->key),
									 fc_query, fc_siglen);
			break;
		case RTSameStrategyNumber:
			if (GIST_LEAF(fc_entry))
			{
				int			fc_i,
							fc_num = ARRNELEMS(fc_query);
				int32	   *fc_ptr = ARRPTR(fc_query);
				BITVECP		fc_dq = palloc0(fc_siglen),
							fc_de;

				while (fc_num--)
				{
					HASH(fc_dq, *fc_ptr, fc_siglen);
					fc_ptr++;
				}

				fc_de = GETSIGN((GISTTYPE *) DatumGetPointer(fc_entry->key));
				fc_retval = true;
				LOOPBYTE(fc_siglen)
				{
					if (fc_de[fc_i] != fc_dq[fc_i])
					{
						fc_retval = false;
						break;
					}
				}

				pfree(fc_dq);
			}
			else
				fc_retval = fc__intbig_contains((GISTTYPE *) DatumGetPointer(fc_entry->key),
										  fc_query, fc_siglen);
			break;
		case RTContainsStrategyNumber:
		case RTOldContainsStrategyNumber:
			fc_retval = fc__intbig_contains((GISTTYPE *) DatumGetPointer(fc_entry->key),
									  fc_query, fc_siglen);
			break;
		case RTContainedByStrategyNumber:
		case RTOldContainedByStrategyNumber:

			/*
			 * 由于从 intarray 1.4 开始，这段代码是无法到达的，因为 <@
			 * 操作符已从操作类中移除。我们暂时保留它以支持旧版本的 SQL 定义。
			 */
			if (GIST_LEAF(fc_entry))
			{
				int			fc_i,
							fc_num = ARRNELEMS(fc_query);
				int32	   *fc_ptr = ARRPTR(fc_query);
				BITVECP		fc_dq = palloc0(fc_siglen),
							fc_de;

				while (fc_num--)
				{
					HASH(fc_dq, *fc_ptr, fc_siglen);
					fc_ptr++;
				}

				fc_de = GETSIGN((GISTTYPE *) DatumGetPointer(fc_entry->key));
				fc_retval = true;
				LOOPBYTE(fc_siglen)
				{
					if (fc_de[fc_i] & ~fc_dq[fc_i])
					{
						fc_retval = false;
						break;
					}
				}
			}
			else
			{
				/*
				 * 不幸的是，由于空数组可能在索引中的任何地方，我们必须搜索整个树。
				 */
				fc_retval = true;
			}
			break;
		default:
			fc_retval = false;
	}
	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_BOOL(fc_retval);
}

Datum g_intbig_options(PG_FUNCTION_ARGS)
{
	local_relopts *fc_relopts = (local_relopts *) PG_GETARG_POINTER(0);

	init_local_reloptions(fc_relopts, sizeof(GISTIntArrayBigOptions));
	add_local_int_reloption(fc_relopts, "siglen",
							"signature length in bytes",
							SIGLEN_DEFAULT, 1, SIGLEN_MAX,
							offsetof(GISTIntArrayBigOptions, siglen));

	PG_RETURN_VOID();
}
